%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%          3rd International Workshop on Cross Enterprise Collaboration,
%                      People and Work (CEC-PAW'12)
% 
% Website: <http://www.cs.helsinki.fi/cec-paw12/call-papers>
% 
% Topics:
%  - Governance, safeguarding and securing management and coordination across
%    the collaborating enterprises and their providers and suppliers.
%  - Deep visibility into all aspects of work and process across an ecosystem of
%    partners, providers, and suppliers. Metrics, sensors, and E2E monitoring
%    that span both the horizontal cross-enterprise collaboration and the
%    vertical stacks of providers and suppliers
%  - Models, methods, formalisms, and languages that focus on the control and
%    coordination of cross-enterprise collaboration in different domains
%    Context, data, and knowledge management as required for managing and
%    coordinating work across organizations and their interrelationship with the
%    domain data, tools, and processes.
%  
% We invite research papers up to 12 pages in length and shorter vision or
% position papers up to 5 pages.
% 
% Dates:
% - submission: July 31, 2012 
% - notification: September 15, 2012
% - camera ready: October 1, 2012
% - workshop: November 12 - 16, 2012
% 
% Organizers:
% - Francisco Curbera, IBM TJ Watson Research Center, USA <curbera@us.ibm.com>
% - Dimka Karastoyanova, University of Stuttgart, Germany
% - Rania Khalaf, IBM TJ Watson Research Center, USA
% - Frank Leymann, University of Stuttgart, Germany
% - Alex Norta, University of Helsinki, Finland
% - Daniel Oppenheim, IBM TJ Watson Research Center, USA
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[
	lnbip,
	runningheads,
%	draft,
%	forInclusion
]{svmultln} % llncs

% encoding and languages
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[ngerman,english]{babel}

% more packages

\usepackage{microtype}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{paralist}
\usepackage[font=small]{caption,subfig} % font=small
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{makeidx}
\usepackage{txfonts}
\usepackage{url}
\usepackage{float}

% include custom modifications
% \newcommand{\final}{}
\usepackage{_style/review}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% document setup

% Search for figures in following directoreis
\graphicspath {{./} {_figures/}}

\usepackage{hyperref}
\usepackage[english]{babel}

\hypersetup{
    % pdftitle={\thetitle},
    % pdfauthor={\theauthormail},
    % pdfsubject={\thesubject},
    % pdfkeywords={\thekeywords},
    breaklinks=true,
    colorlinks=true,
    linkcolor=black,
    citecolor=black,
    urlcolor=black,
    pdfstartpage=1
}

% set up listings style
\lstset{
	basicstyle=\ttfamily,
	showspaces=false,
	showtabs=false,
	columns=fixed,
%	numbers=left,
	frame=none, %tlrb (single) TLRB (double)
	numberstyle=\tiny,
	breaklines=true,
	showstringspaces=false,
	xleftmargin=0.5cm,
%	backgroundcolor=\color[rgb]{0.92,0.92,0.92},
	captionpos=b
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% page setup
\clubpenalty10000
\widowpenalty10000

\newcommand{\examplescale}{0.393}
\hyphenation{}

\newcommand{\vbf}{\vspace{0em}} % vspace before figure
\newcommand{\vaf}{\vspace{0em}} % vspace after figure

%\usepackage[small,compact]{titlesec} % small,


\newcommand{\emp}{T_e} % set of monitoring point transitions
\newcommand{\pre}[1]{{\bullet{#1}}}
\newcommand{\post}[1]{{{#1}\bullet}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% start document
%
\begin{document}
\mainmatter
%
\title{Monitoring Business Process Interaction}
%
%\author{Nico Herzberg \and Matthias Kunze \and Mathias Weske}
\author{Nico Herzberg, Matthias Kunze, Mathias Weske}
%
\institute{Hasso Plattner Institute at the University of Potsdam\\ Prof.-Dr.-Helmert-Strasse 2-3, 14482 Potsdam \\ %
\texttt{\{nico.herzberg,matthias.kunze,mathias.weske\}@hpi.uni-potsdam.de}
}

\maketitle

% abstract ---------------------------------------------------------------------

\begin{abstract}\wording{
	Business process monitoring provides well established means to track the history and state of enacted business processes and to evaluate their performance, while neglecting interactions of a process with its partners by sending and receiving messages. However, most business processes involve interactions, e.g., with customers, suppliers, or service providers.}
	
	\wording{In this paper, we present a mechanism to detect, whether the operations of a process cannot proceed, because it is waiting for an incoming message expected from one of its partners. Based on this mechanism, we provide a formal framework to monitor the process and to evaluate its performance for different monitoring views. 
	The framework has been developed in the context of an industry project, which we also used to evaluate our solution.}
	
	
\keywords{
	monitoring of business processes,
	performance measurement of business processes,
	business process interactions}
\end{abstract}

% introduction -----------------------------------------------------------------
\section{Introduction} \label{sec:introduction}

Business process management has received considerable interest among modern companies, as it sustains competitiveness in an ever changing market environment. Organizations capture their processes in business process models for documentation, but also for automation and certification. Evaluating business processes, in particular with respect to execution performance, requires means to monitor the state of a process instance by tracking business relevant events. Business process monitoring is a well established discipline, and has received considerable support in modern business process management systems~\cite{grigori:2004}. \wording{These systems track the state of a process by means of a technical process model and events that track the beginning and the end of each activity, and decisions taken. Typically, such systems also provide sophisticated support in resource management.}

However, a large ratio of business processes are enacted in a non-automated
manner, i.e., they are not executed by means of a workflow engine but conducted
manually by humans following. Consequently, there is no central record of conducted activities comparable to a process log~\cite{aalst:2004a}, but only few activities, events, or side effects, e.g., a state change of a document, can be observed in the \wording{distributed technical organization} of the business process.

Moreover, many processes involve interaction partners, e.g., in large organizations, several departments collaborate on a joint goal, and interaction between them is not controlled centrally. As the internal processes of interaction partners are unknown, it is difficult to monitor interaction and evaluate performance. \wording{Nevertheless, the ability to monitor and evaluate the performance of a business process is required to adhere to service level agreements or \todo{...}}

% Consider a case, where a service provider agrees to provide a service within a certain amount of time. If requests to the service consumer are not responded in time, the service provider will fail to meet the agreement although he is not responsible for the delay. Hence, organizations perceive a great value in the ability to monitor and evaluate the performance of their interaction with partners in the context of their business processes. Communicating the current state and evaluation of a process among partners also suggests to increase transparency, while hiding internal details, and to make interactions more efficient.

In this paper, we address these obstacles and present a framework to monitor process interaction in absence of a central business process management system. In more detail, we provide a formal framework based on the notion of workflow modules, partner synthesis, and event monitoring points that allows capturing the state of a process even if the track of events is sparse, monitoring process interactions, and detecting whether a partner cannot proceed, because it is waiting for a message from another partner.
Based on this framework, we introduce interaction monitoring models, an abstraction of the internal behavior of a process, as a means to monitor the state of a process on a coarsely grained level, and communicate it to stakeholders in real time. These models provide instant insight into the current state of a process and allow telling who is responsible for a delay. Additionally, we illustrate how the performance of business processes and process interactions can be evaluated in quantitative terms based on this framework.

The remainder of this paper is structured as follows. We motivate process
interaction monitoring with a case study where the proposed framework has been applied, in Section~\ref{sec:motivation}. Section~\ref{sec:solution} provides the formal framework of our approach and explains, how it enables process interaction monitoring and evaluation. We then revisit the motivational use case and discuss its implementation in Section~\ref{sec:implementation}, before we discuss related work in Section~\ref{sec:related_work}, conclude the paper and give a brief outlook on future work, in Section~\ref{sec:conclusion}.

% motivating example -----------------------------------------------------------
\section{Case Study} \label{sec:motivation}

In this section, we present the case of a German health insurance company, who carried out mergers of several federal branches in recent years. These branches independently carried out similar operations for years. However, after the merger it turned out that different job specifications existed for the same position in the company across the former branches. Hence, the \emph{organization development} (OD) department became in charge of harmonizing job specifications.

\begin{figure}[b]\vbf
	\includegraphics[scale=\examplescale]{case_study_bpmn}
	\caption{Job specification harmonization process of a health insurance company
	(simplified model)}
	\label{fig:case_study_bpmn}
\vaf\end{figure}

\figurename~\ref{fig:case_study_bpmn} shows the BPMN~\cite{bpmn20} process model that has been established to harmonize job specifications. It involves several interaction partners: \emph{Quality Assurance} (QA), \emph{Human Resources} (HR), a \emph{Department} that embraces the position to be harmonized, e.g., medical care, geriatric care, IT, and HR, and a \emph{Committee} that eventually approves the harmonized job specifications. It is also possible that one Department engages in several roles, e.g., if a position in Human Resources needs to be harmonized.

In the process model, we see that the OD department starts the process and prepares the job description documents. Subsequently, it requests a description of the position from the respective Department and checks it for completeness upon reception. Please note, that interaction between the departments has been modeled as message passing between separate pools in the model. If the job description from the Department is incomplete, the Department must improve it in an iterative fashion.
	Otherwise, it is handed over to the QA department that ensures that job
	definitions meet the company's requirements. At the same time, Human Resources
	receive the job description with a request to propose a salary for the position. After both inputs have been incorporated, OD department the updates the job specification documents.
	Eventually, the job specification is prepared and sent to the Committee whose sole task is to review and approve the specification. In case it is denied, the respective Department must update it, and it needs to be reviewed again by the Committee.

The OD department strives to harmonize a job specification within three months. However, in a fair amount of cases, one or several of the interaction partners impede progress as they do not respond in a reasonable period of time. Hence, the OD department required a means (a) to track the status of a process instance, i.e., show the current state, show previous actions, and point out, whether the instance is waiting for a response from one partner to answer who is responsible for a delay, and (b) to provide time measurements about the duration of the complete process, its activities, and how much time respective interaction partners have spent for their contributions.

Nevertheless, the OD department was reluctant to disclose their internal,
detailed process model to interaction partners. Therefore, they identified three phases, \emph{job description} (i), \emph{quality assurance} (ii), and \emph{approval} (iii), grouped by dashed boxes in \figurename~\ref{fig:case_study_bpmn}. Above information should then be projected on a simple model of these phases and be presented to the other departments. By that, the OD department offers process monitoring based solely on their knowledge of the process, i.e., the processes of interaction partners are not known, whilst enabling monitoring and performance evaluation of interactions with its partners.

% 
% Following questions shall be answered by an approach towards monitoring interaction.
% 
% \textbf{phases}
% 
% \noindent1. monitoring on a coarse level/hide information\\
% - \textbf{in which phase is a process instance}\\
% - what is the trace of the process instance, for each terminated phase start/end, who was involved\\
% - when did it enter the phase\\
% - \textbf{is the process currently waiting (in a specific phase) for a partner}\\
% - \textbf{how many and which process instances are in a respective state}\\
% 
% \noindent2. performance evaluation\\
% - \textbf{how long do process instances take}\\
% - \textbf{how long does a phase take}\\
% - how much time did a partner contribute to a phase\\
% - how much time has been spent waiting in a phase\\


% the concept/solution ---------------------------------------------------------
\section{Interaction Monitoring Framework} \label{sec:solution}

\wording{
Based on above questions that have been identified for process interaction monitoring, we first introduce workflow modules as basis to capture process interactions formally, in Section~\ref{sub:modeling_interactions}. Subsequently, we show, how monitoring questions can be answered by means of a coarse grained interaction model that maps execution semantics of the underlying workflow modules in Section~\ref{sub:monitoring_interaction}, before we explain how to evaluate process performance based on this model in Section~\ref{sub:measuring interactions}. We briefly discuss basic assumptions and limitations of our approach in Section~\ref{sub:discussion}.
}

\subsection{Modeling Interactions} % ..........................................
\label{sub:modeling_interactions}
To illustrate our approach, we leverage the example process model from Section~\ref{sec:motivation}, cf.~\figurename~\ref{fig:case_study_bpmn}. Here, we assume that the process along with its interaction partners is captured in a detailed model, whereas the process of the partners is generally unknown. For instance, in BPMN, process interaction is modeled through message events and message flow, and partners can be represented as black box pools~\cite{bpmn20}. 

To formalize the interaction between processes, we resort to workflow modules, which have been introduced in~\cite{martens:2003}. Workflow modules are essentially Petri nets---a commonly used formalism for execution semantics of business processes~\cite{aalst:1998}---with additional places that represent  sent and received messages, referred to as input and output places of a module hereafter. 
%
% TODO, do we need the marking?
\begin{definition}[Workflow Module] \label{def:workflow_module}
%
A \emph{workflow module} is a tuple $N = (P,T,F,P_i,P_o)$, where $(P,T,F)$ is a Petri net that consists of finite disjoints sets of places $P$ and transitions $T$, and a flow relation $F \subseteq (P \times T) \cup (T \times P)$.
For $X = {P \cup T}$, we refer to $\pre{x} = \left\{y \in X | (y,x) \in F\right\}$ as the preset and $\post{x} = \left\{y \in X | (x,y) \in F\right\}$ as the postset of a node $x \in X$, respectively.
% [petri net structure]

$P_i \subseteq P$ denotes the set of of input places of $N$, such that
$\forall{p \in P_i}: {\pre{p} = \emptyset}$,
 and 
$P_o \subseteq P$ the set of output places of $N$, such that 
$\forall(p \in P_o) : {\post{p} = \emptyset}$.
No transition is connected to an input place and an output place at the same time, i.e., $\forall{p_i \in P_i, p_o \in P_o} \not\exists {t \in T}: t \in \post{p_i} \wedge t \in \pre{p_o}$. 
% [interface places]
%
% A workflow module without its input and output places is a structurally sound workflow net, i.e., there exists one distinct initial place $i \in P\setminus P_i$ without incoming arcs, i.e., $\pre{i} = \emptyset$ and one final place $o \in P \setminus P_o$ without outgoing arcs, i.e., $\post{o} = \emptyset$, and each transition is on a path between both, i.e., the short-circuited net $N' = ({P \setminus (P_i \cup P_o)}, T \cup\{t_c\}, F \cup \{(o,t_c),(t_c,i)\}), T_c \not\in T$ is strongly connected.
% [structural soundness]
%
The state, or \emph{marking}, of $(P,T,F)$ is defined by a function $M: P \rightarrow \mathbb{N}$. 
% [marking]
\end{definition}
%
For the given process model and each partner, a workflow module needs to be created.  Interaction of the respective partners is modeled by fusing input places of one module with output places of another one, i.e., given the set of workflow modules of a process and its interaction partners, $\mathcal{N}$, it holds that
${\forall{N \in \mathcal{N}}}\; {P_i^N \subseteq {\bigcup_{N' \in {\mathcal{N}\setminus\{N\}}}{P_o^{N'}}}}$, where $P_i^N$ ($P_o^N$) represents the input (output) places of a module $N \in \mathcal{N}$.
Hence, if one module puts a token on one of its output places, this token signals the message transmission, because it is at the same time on the input place of another module. 

The process model is translated into a workflow net following common Petri net-based formalizations~\cite{lohmann:2009}, e.g., activities and events are represented by activities connected through places, diverging (merging) XOR-gateways by a place that has outgoing (incoming) arcs to (from) several transitions, and forking (joining) AND-gateways by a transition that has outgoing (incoming) arcs to (from) several places. Message exchange (dashed arcs in \figurename~\ref{fig:case_study_bpmn}) between the process and a partner is captured by adding input and output places for each incoming and outgoing message~\cite{martens:2003}.

As the processes of the partners are typically not known, they cannot be translated into workflow modules. However, partners that provide compatible behavior to the process can be synthesized from the internal state and the interaction of the process~\cite{wolf:2009}. A synthesized partner describes the observable behavior at the interface between the partner and the process. By that, we can correlate events observed at the interaction interface of the process.

% TODO if space limitations require, we can skip this paragraph 
In the context of process monitoring, internal life cycles for activities have been proposed to be captured, when translating models to Petri nets, e.g., \cite{herzberg:2012}, where one activity would be translated into a subnet that becomes enabled, running, and terminated. However, in the present case, we are only interested in completion of activities or interactions. Hence, an activity or event of the process model can safely be represented as a single transition in the workflow module. Consequently, termination of an activity or event is represented by firing its corresponding transition.

\newcommand{\trn}[1]{${#1}$}            % transition
\newcommand{\txt}[1]{\text{\emph{#1}}}  % text in formula
\newcommand{\snd}[1]{$\txt{!}{#1}$}     % send transition
\newcommand{\rcv}[1]{$\txt{?}{#1}$}     % receive transition

\figurename~\ref{fig:case_study_pn} depicts the fused workflow modules for the
job specification harmonization process and its interaction partners. The module
in the middle of the figure represents the process, which has been translated into a workflow module as presented above, the partner modules (separated by dashed horizontal lines) of the Department, Quality Assurance, Human Resources and the Committee have been synthesized.
For brevity, we used acronyms for activities, e.g., \trn{pJD} represents activity “process job description” and \trn{cc} stands for “check complete”.

BPMN message events have been translated to transitions, whereas sending a message is marked by a leading \emph{!} in the transition label and receiving a message by a leading~\emph{?}.
Here, process interaction typically consists of two messages sent, a request to a partner and the partner's response. For instance, transition \snd{\txt{JD}} stands for requesting a job description. This request is received by the Department, represented through transition \rcv{\txt{JD}_D}, and responded with \snd{\txt{JD}_D}. This response is received by the process through \rcv{\txt{JD}}. The remaining interactions are analogous.

\begin{figure}[t]\vbf
	\includegraphics[scale=\examplescale]{case_study_pn}
	\caption{Workflow modules for the job specification harmonization process, cf.\ \figurename~\ref{fig:case_study_bpmn}. Shaded places represent start places of the modules. The current marking, i.e., distribution of tokens to places, represents a certain state during the execution of one process instance.}
	\label{fig:case_study_pn}
\vaf\end{figure}

It is important to understand that the workflow modules of interaction partners may differ from their actual processes, as these modules only describe the observable behavior of these partners at the interface of the process. One can  understand this as part of the process that is not explicitly modeled. 

% For instance, an input place $p$ represents the in-box at the mail room of the OD department, sending transitions $t \in \pre{p}$ in the fused workflow modules represent dropping a message in that inbox. This enables the actual reception of the message in the process, i.e., when the process is ready to receive, it checks the inbox for the expected message.

% The Petri net in \figurename~\ref{fig:case_study_pn} presents several features worth mentioning. For instance, the process of the department provides more behavior than required by the interaction, as it also allows to fire \emph{?O} and \emph{!O} after \emph{!O\!’}. The central place is required, as the department must react to decision made by the OD department and communicated by sending different messages. This implements the deferred choice workflow pattern~\cite{workflowpatterns}. 

The Committee has, in this particular case, not been modeled as a proper workflow module---it is missing dedicated start and end places. This is due to its sole task to review job specifications, i.e., the Committee may review several job harmonization process instances in the course of one session.  We captured this as a continuous loop in the Committee module. Nevertheless, the fused Petri net is free from dead locks.

\subsection{Monitoring Interaction} % .........................................
\label{sub:monitoring_interaction}

The workflow modules depicted in \figurename~\ref{fig:case_study_pn} are already
marked, i.e., some places contain tokens. Based on a marking, we define the
state and execution semantics of workflow modules as follows.
\begin{definition}[Workflow Module Semantics] Let $(P,T,F,P_i,P_o)$ be a
workflow module and $M$ be a marking.
	\begin{compactitem}
		\item A transition $t \in T$ is enabled, iff 
		$\forall{p \in \pre{t}}: {M(p) \geq 1}$.
%		
		\item A transition $t \in T$ is \wording{waiting}, iff
		${{\forall{p \in {\pre{t}\! \setminus\! P_i}}: {M(p) \geq 1}} \wedge
		{\forall{p \in {\pre{t}\! \cap\! P_i}}: {M(p) = 0}}}$.
%		
		\item The firing of a transition $t$ in state $M$ where $t$ is enabled results in a state $M'$ where $\forall{p \in \pre{t}}: {M'(p) = M(p) - 1} \wedge \forall{p \in \post{t}: {M'(p) = M(p) + 1}}$ % TODO, add symbol for firing?
	\end{compactitem}
\end{definition}
%
In \figurename~\ref{fig:case_study_pn}, the process is in a state where requests for an evaluation of the job specification and for a salary proposal have been sent to Quality Assurance and Human Resources. While Human Resources has already responded with a proposal that has been incorporated into the job specification, i.e., transition \trn{\txt{iSP}} has fired, the process is waiting for a response from Quality Assurance which has not been received yet. Transition \snd{E_{QA}} of Quality Assurance has not fired yet. Since only the token from the input place of \rcv{E} is missing for enablement, transition \rcv{E} is \emph{waiting}.

To monitor a process instance and interaction with its partners, a set of event
monitoring points is required, i.e., information that a state has changed. We
represent these events by special transitions that do not fire until the event
has been observed. Here, we assume such events to be correlated with a process
instance and transitions. A \wording{process monitoring and process performance
evaluation system} that provides event detection and correlation has been
presented in~\cite{herzberg:2012} and is briefly presented in the implementation section, cf.\ Section~\ref{sec:implementation}.
%
\begin{definition}[Event Monitoring Point, Transition Firing] \label{def:monitoring_point}
%
	Let $(P,T,F,P_i,P_o)$ be a workflow module.
	An event monitoring point represents a business event that triggers an observable state change of the net, denoted by the firing of a transition $t \in T$. The set of event monitoring points is defined as $\emp \subseteq T$.
	
	Firing of $t \in \emp$ is deferred until the event related with $t$ has been monitored; all other transitions, i.e., $t \in {T\!\setminus\!\emp}$, fire immediately, when they become enabled.
\end{definition}
%
In \figurename~\ref{fig:case_study_pn}, event monitoring points are visualized by a bold outline. As we discussed in Section~\ref{sec:introduction}, not every activity may be represented by an event in the process environment. However, to keep the paper concise, we require that each decision can be monitored, i.e., transitions that share an input place need to be event monitoring points. One can see that transition \snd{E_\txt{QA}} is enabled. Since a message from Quality Assurance has not been received yet, i.e., the according event has not been detected, \snd{E_\txt{QA}} did not fire.

Above mechanism allows obtaining the current state and history of a process, whether it is waiting, whom it is waiting for, and with which partners it has interacted, by means of workflow modules and a process log, i.e., detected event monitoring points. However, as one may not want to disclose the detailed behavior of a process to external parties, i.e., the interaction partners, we provide a model that hides internal behavior, yet captures interaction of the process with its partners.
%
\begin{definition}[Interaction Monitoring Model, Interaction Semantics]
%
An interaction monitoring model $I = (V,E)$ is a connected graph of finite sets of interaction activities $V$ and directed edges $E \subseteq V \times V$. The interaction activities provide a partitioning of the transitions of a workflow module $(P,T,F,P_i,P_o)$, i.e., $\pi(T) = \{v_1,v_2,...,v_n\}$. 
%
% [comment: partitioning allows a lot of crazy stuff, i.e., even concurrently active activities, but that is ok. We should not restrict this further.]
%
If transitions of two distinct interaction activities, $v_i$, $v_j$, are connected by a place, these interaction activities are connected by an edge, i.e., 
${{{t_r \in v_i} \wedge {t_s \in v_j} \wedge v_i \not= v_j \wedge {\post{t_r}
\cap \pre{t_s}}} \not= \emptyset} \Rightarrow {(v_i,v_j) \in E}$.
%
% [comment: here we connect activities by the underlying PN structures, high entropy partitions will lead to a large number of edges. v-i \not= v_j prevents edges from one activity to itself]
%	
	\begin{compactitem}
		\item An interaction activity ${v \in V}$ is waiting, if there is no transition ${t \in v}$ enabled, but at least one of these  transitions is waiting.
%		\item A waiting transition waits for every partner that embraces an enabled transition, i.e., \todo{...}
		\item An interaction activity ${v \in V}$ is active, if there is at least one transition ${t \in v}$ that is enabled or waiting.
	\end{compactitem}	
\end{definition}
%
Essentially, an interaction model is an abstraction of the process' workflow module. Different techniques for automatic abstraction have been presented, e.g., \cite{polyvyanyy:2009}, but they are not in the scope of this paper. We rather assume that abstraction addresses specific requirements of the use case at hand, i.e., to provide partners with a perspective on the state of the interaction, while hiding sensitive information from them. 

In \figurename~\ref{fig:case_study_pn}, the partitioning of transitions is represented by three dashed rectangles (i--iii) that correspond to the phases of the process that have been identified, cf.\ Section~\ref{sec:motivation}. The resulting interaction monitoring model is illustrated in \figurename~\ref{fig:case_study_interaction}, which shows the interaction activities that embrace the corresponding transitions, their involved partners, and their state derived from the marking of the workflow module. A legend is provided in \figurename~\ref{fig:legend}.

\hspace{-1.8em}
\begin{minipage}[b]{0.48\textwidth}\vbf
	\begin{figure}[H]
		\begin{center}
		\includegraphics[scale=\examplescale]{case_study_interaction}
		\caption{Interaction monitoring model for the job specification harmonization process}
		\label{fig:case_study_interaction}
		\end{center}
	\vaf\end{figure}
\end{minipage}
\hspace{0.02\textwidth}
\begin{minipage}[b]{0.49\textwidth}
	\begin{figure}[H]\vbf
		\begin{center}
			\includegraphics[scale=\examplescale]{case_study_legend}
			\caption{Interaction monitoring model, notation legend.}
        	\label{fig:legend}
		\end{center}
	\vaf\end{figure}
\end{minipage}

Based on the marking of transitions $t \in v$, we can deduce the state of an interaction activity. If there is at least one transition that is either enabled or waiting, the interaction activity is considered active, as operations may be carried out. If an interaction activity contains only disabled and at least one waiting transitions, then it cannot proceed until the respective messages are received and the waiting transitions fire. Nevertheless, also a waiting activity is active, because in a future point in time, it can proceed.

From the fused workflow modules we know the partner for every transition that is connected with an input or output place, respectively. Hence, for any marking of the net, we can decide, which of the activities are active and which are waiting, and for which partners an activity is waiting.

The interaction activity ``Quality Assurance'' (ii) is in state
waiting, as no transition in the corresponding partition can fire, but
transition \snd{E_\txt{QA}} is waiting. Hence, the whole activity waits for the
input from Quality Assurance. This is illustrated in the interaction monitoring
model by a an active (shaded) partner that is annotated with an hourglass. As Human Resources already provided their input and will no further interact with the process in the current interaction activity, the corresponding participant symbol is not shaded, indicating inactivity. Interaction partners of future activities are also shaded as they may be involved as the process advances.

\subsection{Measuring Interaction Performance} % ......................
\label{sub:measuring interactions}

In order to accurately derive the state of each activity of an interaction
monitoring model and to compute performance measures on the same level of
granularity, a minimal set of event monitoring points is required. This
incorporates a monitoring point for each sent and received message, i.e.,
${\forall {p \in (P_i \cup P_o)} : {\pre{p} \subseteq \emp}}$, and one
monitoring point for every possibility to enter and leave activities, i.e., for
all $t_r \in v_i, t_s \in v_j$ such that $(v_i,v_j) \in E \wedge \post{t_r} \cap
\pre{t_s} \not= \emptyset$ we require that $t_r, t_s \in \emp$.

From these information, calculation of various performance measures becomes possible. For instance, the duration of an activity is computed by subtracting from the time of the latest detected event monitoring point the time of the earliest detected monitoring point that belongs to this activity. From active and waiting states of transitions, we can compute the amount of time the activity was actually waiting for input from a specific partner, if at least one received message followed an earlier sent message.

Consider, for an example, interaction activity ``Job Description'' represented
by the leftmost dashed rectangle in \figurename~\ref{fig:case_study_pn} and the
following log entries, i.e., pairs of event monitoring point and point in time.
(Here we refer to the first unlabeled transition as \trn{\tau}).
\wording{\{%
	(\trn{\tau},       0),
	(\snd{\txt{JD}},   3),
	(\snd{\txt{JD}_D}, 7),
	(\trn{cc},         8),
	(\snd{\txt{JD}},   9),
	(\snd{\txt{JD}_D}, 11),
	(\trn{cc},         13)%
\}}. After one iteration was required to complete the job description, the result provided from the Department was accepted eventually. In this interaction activity instance, the process was active \wording{$13$} time units, of which it was waiting \wording{$(7-3)+(11-9) = 6$} time units for the Department.

The overall process duration needs to be computed from the first and the last event monitoring point that have been detected. It is not possible to sum the durations of the interaction activities, as they may be active or waiting concurrently. 
%
Finally, computation of statistics, e.g., average or median execution durations for process and interaction activities, is carried out by aggregating durations computed from distinct process instances.

\subsection{Assumptions and Limitations}
\label{sub:discussion}

Our approach to monitor process interactions is subject to certain assumptions and limitations. First, we assume that, for every partner, we can synthesize a behavior and the combined behavior, i.e., by fusing input and output places of the process with output and input places of partners, yields a model that can be transformed into a workflow net which is weak sound~\cite{martens:2003}---a correctness property that ensures the absence of deadlocks, while not all transitions of a workflow module need to be executable. 

Further, we require that every process instance strictly follows the model,
i.e., event monitoring points are only discovered, when the respective
transitions are enabled. Violation of the model could be mitigated by relaxed firing semantics of the model, e.g., if there exists a sound firing sequence that leads to a marking that allows firing an event monitoring point transition, we could accept the event monitoring point. Yet, this is not in the focus of this paper and shall be addressed in future work.

In an interaction monitoring model, edges represent only relaxed ordering semantics of interaction activities. An edge indicates that from one activity another may follow, however, two interaction activities that are connected by an edge may be active concurrently. Also, activities may be skipped. More accurate semantics of these edges could be defined by restricting the abstraction provided through the partitioning of transitions. However, the given abstraction proved effective in practice, cf.\ Section~\ref{sec:implementation}: In most cases, a coarse-grained differentiation in subsequent process phases is desired.

We resorted to a rather simplistic visual representation of the interaction monitoring model, as the focus of this paper is on the framework to track interaction, detect waiting states, and derive performance evaluations. Much more information can be derived from the workflow modules' structure and the record of event monitoring points, e.g., how often have certain messages been sent, how long did each of these interactions take, and whether interaction activities have been active several times and, if so, how often.

% case study -------------------------------------------------------------------
\section{Implementation} \label{sec:implementation}

%\todo{brief system architecture that shows event monitoring platform, where
% vent correlation happens, and on top the monitoring and analysis layer that contains the contribution here, then focus on outcome, e.g., case\_study\_evaluation diagram}

% Recapitulate the job specification harmonization process in \figurename~\ref{fig:case_study_bpmn} from Section~\ref{sec:motivation}. We transformed the process into a workflow module and constructed partner modules that provide compatible behavior. Fusing input and output places resulted in the Petri net model depicted in \figurename~\ref{fig:case_study_pn}. Again, for brevity, we used abbreviations for sending (\emph{!}) and receiving (\emph{?}) message events and tasks. 
% 
% 
% 
% 
% It is important to understand that the workflow modules of interaction partners may differ with their actual processes, as these modules do only describe the observable behavior of these partners at the interface of the process. One can  understand this as part of the process that is not explicitly modeled. For instance, an input place $p$ represents the in-box at the mail room of the OD department, sending transitions $t \in \pre{p}$ in the fused workflow modules represent dropping a message in that inbox. This enables the actual reception of the message in the process, i.e., when the process is ready to receive, it checks the inbox for the expected message.
% 
% The Petri net in \figurename~\ref{fig:case_study_pn} presents several features worth mentioning. For instance, the process of the department provides more behavior than required by the interaction, as it also allows to fire \emph{?O} and \emph{!O} after \emph{!O\!’}. The central place is required, as the department must react to decision made by the OD department and communicated by sending different messages. This implements the deferred choice workflow pattern~\cite{workflowpatterns}. 
% 
% The committee has, in this particular case, not been modeled as a proper workflow module, as its sole task is to review job specifications, i.e., for each request to review a job specification, a new review instance is started, even if several requests stem from the same instance of a harmonization process. We captured this as a global loop in the committee module. Nevertheless, the fused Petri net is free from dead locks.
% 
% The dashed rectangles of the harmonization process workflow module visualize the partitioning provided by the interaction activities in \figurename~\ref{fig:case_study_interaction}.

\wording{The architecture of a process monitoring and process performance
evaluation system shown in \figurename~\ref{fig:architecture} is based on an
event capturing functionality that captures the event information from various
sources. Recapitulate our motivating use case of the job specification
harmonization, the events used for monitoring are captured from excel files and
business systems. The event information captured is used for particular process
instances (event detection), i.e., harmonization of job specification `clerk for
private patients`, and correlated to the relevant activity in the process (event
correlation).
	Once the event information are correlated to the process and its activities,
	the process monitoring and process performance evalutaion can build on this and
	provide the requested information to the user of the  system in a visual way.}

\hspace{-1.8em}
\begin{minipage}[b]{0.48\textwidth}\vbf
	\begin{figure}[H]
		\begin{center}
		\includegraphics[scale=\examplescale]{architecture}
		\caption{Architecture of a process monitoring and process performance
		evaluation system}
		\label{fig:architecture}
		\end{center}
	\end{figure}
	\vaf
\end{minipage}
\hspace{0.02\textwidth}
\begin{minipage}[b]{0.49\textwidth}\vbf
	\begin{figure}[H]
		\begin{center}
		\includegraphics[scale=\examplescale]{case_study_evaluation}
		\caption{Sample report on time spent in different phases of the process}
		\label{fig:case_study_evaluation}
		\end{center}
	\end{figure}
	\vaf
\end{minipage}

Regarding monitoring and performance evaluation, the health insurance company used the interaction monitoring model to share the state of every process instance with all involved partners. That is, the respective Department can follow progress of its case, while all involved partners can see, whether the process is stuck due to a missing message. Internally, the OD department uses insights from a more detailed model, i.e., on the same granularity level as the workflow modules, to discover causes for delays and identify cases that violated or are likely to violate the aspired maximum duration three months to carry out a process instance.

On the executive level, information of this model is used to evaluate the time spent for harmonizing job specifications and to benchmark the performance of different departments in the context of this process, i.e., to compare response times of the departments and investigate potential bottlenecks at their site. \figurename~\ref{fig:case_study_evaluation} provides a (virtual) bar chart that shows, how much time the respective departments spent within the various phases. The diagram shows average values of time shares among the four departments \emph{medical care} (MC), \emph{geriatric care} (GC), IT, and HR, i.e., each bar segment shows how much time each interaction partner contributed to a given phase, whereas the height of a bar shows the length of the phase. Since the phases are subsequent to one another, the average process duration can be computed by summing the durations of the respective phases.
From the diagram, we can derive that processes involving the MC and GC department have, in average, met the three months (13 weeks) constraint, whereas cases of the IT and HR department took over 13 weeks in average.

% related work -----------------------------------------------------------------
\section{Related Work} \label{sec:related_work} 

Capabilities to monitor, visualize, and evaluate business process execution are
perceived one of the core topics addressed by business process intelligence
(BPI)~\cite{mutschler:2006}, which addresses ``managing process execution
quality by providing several features, such as analysis, prediction, monitoring,
control, and optimization''~\cite{grigori:2004}. Several works discuss the
capturing and storing of process execution data for evaluation purposes
~\cite{grigori:2004,azvine:2006,melchert:2004}, but disregard how this
information can be used to monitor process interactions.

In~\cite{mutschler:2006}, the authors argue that process monitoring and analysis are vital to BPI and propose, based on the specific requirements of BPI, a reference architecture, composed of an integration layer, a functional layer, and a visualization layer.
	The framework presented in this paper targets at the functional and the visualization layer, i.e., provides means to relate monitoring points with business process state and derive insights. We do not address technical questions, e.g., how actual events are detected in the process environment, and how they are correlated with event monitoring points. A solution approach to this is presented in~\cite{herzberg:2012}.

Dahayanake et al.~\cite{dahanayake:2011} give an overview of business activity monitoring (BAM) and introduces four classes of BAM systems: pure BAM, discovery-oriented BAM, simulation-oriented BAM, and reporting-oriented BAM. The first is similar to traditional process monitoring, i.e., provides notifications about a certain state, which is already provided by event monitoring points that found the basis of our approach. Reporting-oriented BAM provides a performance context for running processes and is quite similar to the use case we aim for, where the actual state of a process instance is provided as well as information about the performance evaluation at this stage.

With regards to business process evaluation, the concept of process performance indicators (PPI), the process related form of key performance indicators, is introduced in BPM. Del-Río-Ortega et al.~\cite{del:2010} introduce an ontology to define PPIs for measuring process execution performance, such as time, costs, and occurrences. These PPIs can be applied directly on top of our framework, as it provides measurements that can be compared to target values. As these measures can already be provided while the process instance is running, violations of tolerance thresholds can be mitigated before the process instance failed a PPI.

As mentioned earlier, none of the above research addressed monitoring of business process interactions. Rinderle-Ma et al.~\cite{rinderle:2004} discuss the need of process views to strengthens the understanding of a business process according to the users needs. In the same vein, the requirements for a process monitoring system for system-spanning business processes are discussed and evaluated in~\cite{bobrik:2005}.
	The requirements drawn in that work lead the authors to a monitoring framework for visualizing the execution of business processes~\cite{bobrik:2008}, where interaction diagrams are advocated as one of the most suitable forms to show interaction between several parties participating in a business process execution. However, execution information about partner interaction, such as waiting for a partner's input, are not discussed.
	\wording{\cite{muehlen:2011} discusses collaborations aspects of so-called
	federated tasks that need to be done by participants of different organizations
	resp. companies. In that work the problem of temporal dependencies of tasks
	between interacting organizations is raised as well, but the authors owe the
	reader an answer. \cite{Wagner:2011a} presents an approach how collaboration
	between partners could be simplified by shifting it to the cloud. In this
	setting interaction monitoring capabilities are provided, because workflow engines one both partner sites as well as in the cloud are assumed.
	However, in our setting neither the organization running the process nor the partners that need to contribute having a workflow engine in place; a cloud with a workflow engine is not applicable in this setting.}

The majority of approaches to process monitoring does not target on monitoring and analysis of interaction with partners during process execution. Especially information about partners that are waiting for a message and according performance evaluations are not addressed so far.
	The presented framework provides the techniques to detect waiting states and derive information about the responsibilities in a certain interaction activity.

% conclusion -------------------------------------------------------------------
\section{Conclusion} \label{sec:conclusion}

In this paper we presented a formal framework to capture and express monitoring
of business process interactions in non-automated process execution
environments.
The framework is based on a mechanism to detect whether certain activities of a running process cannot proceed as they are waiting for a message from a partner. Abstraction of the detailed process can be used to define the context of performance evaluation and to provide monitoring to external parties such as interaction partners.

We neglect technical aspects, e.g., how events can be detected in a process environment and how they should be correlated with process instances and certain state changes, because this has already been addressed in earlier work.

In a case study from an industry project, we showed how the approach has been applied to derive an interaction monitoring model, and how certain performance evaluations are computed by means of the developed framework. The resulting process interaction monitor increased transparency among the processes of interaction partners, yet keeping partners independent in their actions, and proved effective in reducing process delays.

In future work, we shall address advanced scenarios that arise from the given limitations and assumptions of our approach. Probably, the most challenging assumption is strict execution compliance, i.e., process executions strictly follow the model. While this has proved effective in the aforementioned use case, it does not generally hold. Different techniques to discover violations of the model's prescription, e.g., an event has been detected although the according monitoring point was not enabled, need to be analyzed.

Based on workflow modules, it is possible to detect, when a process model
exhibits certain flaws, e.g., a partner might still wait for a message, while the process has already terminated. By means of model checking, such deficiencies can be mitigated and lead to improved process models that reveal partner interaction.

While we argue that process performance indicators can be applied on top of our framework, an implementation is still missing and shall also be addressed in future work.
	
\bibliographystyle{plain}
\bibliography{refs} 
% eventually (for submission) replace this with the content of index.bbl

\end{document}
